Nachfolgend werden die wichtigen Sicherheitsmodelle in Bezug auf Public-Key-Verfahren behandelt.

\subsubsection{Sicherheit des privaten Schlüssels}

Ein Public-Key-Verfahren ist sicher, wenn der private Schlüssel nicht in vertretbarer Zeit aus dem öffentlichen Schlüssel ermittelt werden kann. Um dies zu erfüllen bedienen sich die bekannten Verfahren schwer lösbaren Berechnungsproblemen aus der Zahlentheorie. Es ist allerdings nicht sicher, ob diese auch zukünftig schwierig sein werden. Beispielsweise ist bekannt, dass Quantencomputer gängige Public-Key-Verfahren unsicher machen. Es ist aber nicht bekannt, ob und wann solche Rechner gebaut werden können. Eine Sicherheitsinfrastruktur sollte deshalb die einfache Austauschbarkeit zu Grunde liegender kryptografischer Basistechniken gewährleisten.

\subsubsection{Semantische Sicherheit}

Um nachzuweisen, dass ein Public-Key-Verfahren sicher ist, wird ein Sicherheitsmodell benötigt. Sie gelten derzeit als sicher gegen passive Angriffe, wenn sie semantisch sicher sind. Die Beschreibung erfolgt anhand eines Spiels, das bereits aus der Präsenzwoche bekannt ist. Beschrieben wird das Sicherheitsziel \glqq Indistinguishability\grqq (Ununterscheidbarkeit) bei einer \glqq Chosen Plaintext Attack\grqq. Dies wird als Sicherheitsstufe IND-CPA bezeichnet. Die Beschreibung des Spiels erfolgt anhand von Abbildung \ref{ind_cpa}.

Anmerkung: Die Begriffe \glqq Ununterscheidbarkeit\grqq und \glqq semantische Sicherheit\grqq sind im Skript aus der Präsenzwoche erklärt und gleichbedeutend.

\begin{figure}[htbp]
\centering
\fbox{\includegraphics[width=1.0\textwidth]{ex4/images/ind_cpa.png}}
\caption{Spiel zur Sicherheitsstufe IND-CPA}
\label{ind_cpa}
\end{figure}

Der Böse gewinnt, wenn er den richtigen Klartext rät. Die semantische Sicherheit ist gegeben, wenn der Böse das Spiel nicht mit einer Wahrscheinlichkeit deutlich größer als 50\% gewinnen kann. In diesem Fall kann der Böse nichts über den Klartext aus dem Chiffretext erfahren. Semantisch sichere Verschlüsselungsverfahren müssen randomisiert sein, wie in \buchmann{4.3.2} begründet wird.

\subsubsection{Chosen-Ciphertext-Sicherheit}

Wann Public-Key-Verfahren derzeit als sicher gegen aktive Angriffe gelten, wird im nachfolgenden Spiel beschrieben. Beschrieben wird das Sicherheitsziel \glqq Indistinguishability\grqq (Ununterscheidbarkeit) bei einer \glqq Adaptive Chosen Ciphertext Attacke\grqq. Dies wird als Sicherheitsstufe IND-CCA2 bezeichnet. Die Beschreibung des Spiels erfolgt anhand von Abbildung \ref{ind_cca2}.

\begin{figure}[htbp]
\centering
\fbox{\includegraphics[width=1.0\textwidth]{ex4/images/ind_cca2.png}}
\caption{Spiel zur Sicherheitsstufe IND-CCA2}
\label{ind_cca2}
\end{figure}

In diesem Spiel darf der Angreifer alles machen außer den Schlüsseltext $c$ entschlüsseln lassen. Er gewinnt, wenn er den richtigen Klartext rät. Ein Public-Key-Verfahren ist sicher gegen Chosen-Ciphertext-Angriffe, wenn der Böse das Spiel nicht mit einer Wahrscheinlichkeit deutlich größer als 50\% gewinnen kann. In diesem Fall kann der Böse nichts über den Klartext aus dem Chiffretext erfahren.

Verfahren, die diese Bedingung erfüllen, bieten einem Angreifer auch keine Möglichkeit, den Schlüsseltext so zu ändern, dass sich der Klartext in kontrollierter Weise ändert. Diese Eigenschaft nennt man \glqq Non-Malleability\grqq (Nicht-Verformbarkeit).

\subsubsection{Sicherheitsbeweise}

Es sind keine beweisbar schwierigen - d.h. nicht mit polynomiellem Aufwand lösbare - Probleme der Zahlentheorie bekannt, die im Zusammenhang mit Public-Key-Verfahren genutzt werden können. Deshalb existieren auch keine nachweisbar sicheren Public-Key-Verschlüsselungsverfahren.

Aus diesem Grund wird geprüft, ob das Verfahren sicher ist, so lange wenige, klar definierte Probleme schwierig zu lösen sind. Diese Eingrenzung auf wenige mathematische Probleme wird als \textbf{Sicherheitsreduktion} bezeichnet. Die Schwierigkeit dieser Punkte muss beobachtet werden. Sobald ein einziges dieser Probleme einfach zu lösen ist, gilt das Verfahren unsicher.